The ACO Seminar (2024–2025)

Strong spatial mixing (SSM) is an important and widely studied quantitative notion of "correlation decay" for a variety of natural distributions arising in statistical physics and theoretical computer science. One of the most widely studied such distributions is the uniform distribution over proper $q$-colorings on a maximum degree $\Delta$ graph, $\mu$. Provided that $q \ge \Delta + 1$, any such graph has at least one proper $q$-coloring that can be identified via e.g. a greedy search. It is a longstanding folklore conjecture that whenever $q$ satisfies this minimal inequality, $\mu$ exhibits SSM and the correlations between the colors of vertices in a sample from $\mu$ decay exponentially fast in the graph distance between the vertices. However, even the specialization of this basic question to bounded-degree trees has remained wide open, highlighting how much there still is to learn about random colorings.

We essentially resolve the SSM conjecture on trees, holds for random $q$-colorings on trees of maximum degree $\Delta$ whenever $q \ge \Delta + 3$. In the algorithmic direction, we use SSM on trees to establish optimal mixing of the Glauber dynamics (a classical Markov chain) for sampling $q$-colorings on graphs of maximum degree $\Delta$ and girth $\girth$ whenever $q \ge \Delta+3$. We discuss failures of this style of reduction to extend more generally to all graphs.

Includes joint work with Zongchen Chen, Kuikui Liu, and Ankur Moitra and with Kuikui Liu and Francisco Pernice.